1. Field of the Invention
The present invention relates to any field such as cryptography and coding where pseudo random numbers are used.
2. Description of Related Art
In many communication and cryptography algorithms, pseudo-random numbers are generated using modular arithmetic. The pseudo-random number S(i) of index ‘i’ is generated using the formula, (1), below.S(i)=νimod p  (1)where p is a modulus greater than or equal to 3. In generation of Galois fields, p is often a prime number, and in other algorithms p is often the product of 2 relatively prime numbers.
The value ν is usually the prime root of the prime p in the application of Galois field generation. In many cryptographic applications it is the plaintext to be encrypted or other function to be randomized using the index ‘i’.
Random number generation can also be done in an iterative manner using the equivalent formula, (2), below.S(i)=[ν*S(i−1)]mod p  (2)
However sometimes the index usage of ‘i’ is not sequential and it is not possible to use the iterative method. In this situation, all of the possibilities for S(i) need to be stored in a RAM by calculating them iteratively for a particular p, and a particular pseudo random number S(i) is then selected from the RAM as needed using an index.
In certain applications it is desired to reduce the overhead associated with pre-calculating all the S(i) values every time p changes. For example if p were changing frequently, then the overhead of calculating all of the possible S(i) would be enormous. This leaves the choice of storing all of the possible S(i) for all possible p in a RAM which could be enormous, or calculating S(i) on-the-fly using formula (1) above. The challenge with calculating S(i) on the fly is that to implement equation (1) directly in hardware could lead to enormous bit widths for certain applications making it infeasible to calculate on the fly.